【换根DP】洛谷 P6419 [COCI2014-2015 1] Kamp
2022-03-31 23:03:00 # ACM

题链

https://www.luogu.com.cn/problem/P6419

题解

  1. 给一棵树 n 个节点，K 个人的家分布在不同节点上，K 个人会在节点 i 处聚会，如果在 i 处聚会，需要送每一个人回去，那么在 i 处聚会最后把 K 个人送回家的最短时间就是 ans[i]，求在哪些节点举办聚会 ans 最小，输出最小时间和对应的某些节点。
  2. 可以分为两部分求 :
    • f[u] 表示以 u 节点为聚会点，车载 K 个人送回家并回到 u 节点的最短路程
    • mxlen[u] 表示以 u 节点为聚会点，到某个人家的最长路径长度
    • 可知 ans[u] = f[u] - mxlen[u];
  3. 假设以 1 为根，sz[u] 为以 u 为根节点的子树下的人的个数
  4. 如何求 f[u] :
    • 设 g[u] 为以 u 为根的子树，从 u 出发把子树下所有人送回家又回到 u 的最短路程
    • g[u] = sum( g[v] + dis(u, v)*2 ); (sz[v] > 0) 得在 v 子树下有人家的情况下更新
    • 以上是第一次 dfs
    • f[1] = g[1];
    • 更新 f[v] 有三种情况 :
      • f[v] = g[v]; (sz[v] == K) 也就是所有人都在 v 的子树下
      • f[v] = f[u] + dis(u, v)*2; (sz[v] == 0) 也就是所有人都在 v 的父节点 u 的上面(就是不在 v 这棵子树下)
      • f[v] = f[u]; (其他) 也就是不仅在 v 的子树下有人家，v 的子树外也有
    • 以上是第二次 dfs
  5. 如何求 mxlen[u] :
    • 先将 mxlen[u] 定义为以 u 为根节点的子树，从 u 出发到达子树下某个人家的最长链路
    • mxid[u] 定义为以 u 为根节点的子树，从 u 出发到达子树下某个人家的最长链路的第一步走到的孩子节点 v
    • cmxlen[u] 定义为以 u 为根节点的子树，从 u 出发到达子树下某个人家的次长链路且链路不与最长链路有交集
    • 如何得到该定义下的 mxlen[u], mxid[u], cmxlen[u]:
      • mxlen[u] = mxlen[v] + dis(u, v); (sz[v] > 0) 得在 v 子树下有人家的情况下更新
      • cmxlen[u] 和 mx[id] 顺带维护就好了
    • 以上是第一次 dfs
    • 为了求得 mxlen[u] 的真正含义，有好几种情况需要考虑 :
      • 当 (sz[v] == 0)，也就是最长链肯定不在 v 的子树下
        • mxlen[v] = mxlen[u] + dis(u, v); mxid[v] = u;
      • 当 (sz[v] == K)，也就是最长链肯定在 v 的子树下
        • 那么 mxlen[v] 就不需要更新
      • 否则就是 v 的子树下有人家，并且父节点 u 的上面(也就是除了 v 子树)也有节点
        • if( mxlen[u] + dis(u, v) >= mxlen[v] && mxid[u] != v )，此时更新 mxlen[v], cmxlen[v], mxid[v]
        • if( mxlen[u] + dis(u, v) >= mxlen[v] && mxid[u] == v )，此时最长链路不能更新，因为 v 不作为链路的一端
        • if( cmxlen[u] + dis(u, v) >= mxlen[v] )，此时次长链肯定不会经过节点 v，因为如果经过，那么在最长链中就已经更新过了，轮不到这个 if，于是更新 mxlen[v], cmxlen[v]
        • if( mxlen[u] + dis(u, v) >= cmxlen[v] && mxid[u] != v )，此时更新 cmxlen[v]
        • if( mxlen[u] + dis(u, v) >= cmxlen[v] && mxid[u] == v )，此时次长链路不能更新，因为 v 不作为链路的一端
        • if( cmxlen[u] + dis(u, v) >= cmxlen[v] )，此时次长链肯定不会经过节点 v，因为如果经过，那么在前面更新次长链中就已经更新过了，轮不到这个 if，于是更新 cmxlen[v]
    • 以上是第二次 dfs

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>
using namespace std;
#define MS 500009
#define LL long long 

int n, m, k;
int pos[MS];
struct node{
    int poi, cost;   
};
vector<node > vc[MS];
int sz[MS];
LL g[MS], f[MS];
LL mxlen[MS], cmxlen[MS];
int mxid[MS];

void dfs1(int u, int fa){
    if(pos[u]) sz[u] = 1;
    for(auto nb:vc[u]){
        auto v = nb.poi;
        auto c = nb.cost;
        if(v == fa) continue;
        dfs1(v, u);
        if(sz[v]){
            g[u] += g[v] + c * 2;
            if(mxlen[v] + c >= mxlen[u]){
                cmxlen[u] = mxlen[u];
                mxlen[u] = mxlen[v] + c;
                mxid[u] = v;
            }
            else if(mxlen[v] + c > cmxlen[u]){
                cmxlen[u] = mxlen[v] + c;
            }
        }
        sz[u] += sz[v];
    }
}

void dfs2(int u, int fa){
    for(auto nb:vc[u]){
        auto v = nb.poi;
        auto c = nb.cost;
        if(v == fa) continue;
        if(sz[v] == m){
            f[v] = g[v];
        }
        else if(sz[v] == 0){
            f[v] = f[u] + c * 2;
            mxlen[v] = mxlen[u] + c;
            mxid[v] = u;
            if(cmxlen[u] != 0) cmxlen[v] = cmxlen[u] + c;
        }
        else{
            f[v] = f[u];
            if(mxlen[u] + c >= mxlen[v] && mxid[u] != v){
                cmxlen[v] = mxlen[v];
                mxlen[v] = mxlen[u] + c;
                mxid[v] = u;
            }
            else if(cmxlen[u] + c >= mxlen[v]){
                cmxlen[v] = mxlen[v];
                mxlen[v] = cmxlen[u] + c;
                mxid[v] = u;
            }
            else if(mxlen[u] + c >= cmxlen[v] && mxid[u] != v){
                cmxlen[v] = mxlen[u] + c;
            }
            else if(cmxlen[u] + c >= cmxlen[v]){
                cmxlen[v] = cmxlen[u] + c;
            }
        }
        dfs2(v, u);
    }
}

void solve(){
    cin >> n >> m;
    for(int i=2;i<=n;i++){
        int u, v, w; cin >> u >> v >> w;
        vc[u].push_back({v, w});
        vc[v].push_back({u, w});
    }
    for(int i=1;i<=m;i++){
        int x; cin >> x;
        pos[x]++;
    }
    dfs1(1, 0);
    f[1] = g[1], dfs2(1, 0);
    for(int i=1;i<=n;i++) cout << f[i] - mxlen[i] << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    int ce = 1;
    while(ce--) solve();
    
    return 0;
}
Prev
2022-03-31 23:03:00 # ACM